package org.cabbage.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MajorityNumber2 {

    public static void main(String[] args) {
        MajorityNumber2 mn = new MajorityNumber2();
        List<Integer> nums = Arrays.asList(2, 3, 4, 2, 3, 4, 1, 4, 1, 1, 4);
        System.out.println(mn.majorityNumber(new ArrayList<Integer>(nums)));
    }

    public int majorityNumber(List<Integer> nums) {
        Integer temp = null;
        Integer temp2 = null;

        int total = 0;
        int total2 = 0;

        int count = 0;
        int count2 = 0;
        for (int num : nums) {
            if (count == 0) {
                temp = num;
                total = 0;
            } else if (count2 == 0) {
                temp2 = num;
                total2 = 0;
            }
            if (temp == num) {
                count++;
                total++;
            } else if (temp2 == num) {
                count2++;
                total2++;
            } else {
                count--;
                count2--;
            }
            ;
        }

        total = 0;
        total2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            int num = nums.get(i);
            if (num == temp) {
                total++;
            } else if (num == temp2) {
                total2++;
            }
        }

        if (total > total2) {
            return temp;
        } else {
            return temp2;
        }
    }
}
